- Title
- kNN-Borůvka-GPU: a fast and scalable MST construction from kNN graphs on GPU
- Creator
- Arefin, Ahmed Shamsul; Riveros, Carlos; Berretta, Regina; Moscato, Pablo
- Relation
- 12th International Conference on Computational Science and Its Applications (ICCSA 2012). Computational Science and Its Applications - ICCSA 2012: 12th International Conference, Salvador de Bahia, Brazil, June 18-21, 2012, Proceedings, Part 1 (Salvador de Bahia, Brazil 18-21 June, 2012) p. 71-86
- Publisher Link
- http://dx.doi.org/10.1007/978-3-642-31125-3_6
- Publisher
- Springer Berlin Heidelberg
- Resource Type
- conference paper
- Date
- 2012
- Description
- Computation of the minimum spanning tree (MST) is a common task in numerous fields of research, such as pattern recognition, computer vision, network design (telephone, electrical, hydraulic, cable TV, computer, road networks etc.), VLSI layout, to name a few. However, for a large-scale dataset when the graphs are complete, classical MST computation algorithms become unsuitable on general purpose computers. Interestingly, in such a case the k-nearest neighbor (kNN) structure can provide an efficient solution to this problem. Only a few attempts were found in the literature that focus on solving the problem using the kNNs. This paper briefs the state-of-the-art strategies for the MST problem and a fast and scalable solution combining the classical Borůvka’s MST algorithm and the kNN graph structure. The proposed algorithm is implemented for CUDA enabled GPUs (kNN-Borůvka-GPU), but the basic approach is simple and adaptable to other available architectures. Speed-ups of 30-40 times compared with CPU implementation was observed for several large-scale synthetic and real world data sets.
- Subject
- minimum spanning tree; nearest neighbours; parallel computing; CUDA; GPU
- Identifier
- http://hdl.handle.net/1959.13/1306687
- Identifier
- uon:21225
- Identifier
- ISBN:9783642311246
- Language
- eng
- Reviewed
- Hits: 1997
- Visitors: 2403
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|